{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If a String Can Break Another String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkIfCanBreak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查一个字符串是否可以打破另一个字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s1</code>&nbsp;和&nbsp;<code>s2</code>&nbsp;，它们长度相等，请你检查是否存在一个&nbsp;<code>s1</code>&nbsp; 的排列可以打破 <code>s2</code>&nbsp;的一个排列，或者是否存在一个&nbsp;<code>s2</code>&nbsp;的排列可以打破 <code>s1</code> 的一个排列。</p>\n",
    "\n",
    "<p>字符串&nbsp;<code>x</code>&nbsp;可以打破字符串&nbsp;<code>y</code>&nbsp;（两者长度都为&nbsp;<code>n</code>&nbsp;）需满足对于所有&nbsp;<code>i</code>（在&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;之间）都有&nbsp;<code>x[i] &gt;= y[i]</code>（字典序意义下的顺序）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = &quot;abc&quot;, s2 = &quot;xya&quot;\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>&quot;ayx&quot; 是 s2=&quot;xya&quot; 的一个排列，&quot;abc&quot; 是字符串 s1=&quot;abc&quot; 的一个排列，且 &quot;ayx&quot; 可以打破 &quot;abc&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = &quot;abe&quot;, s2 = &quot;acd&quot;\n",
    "<strong>输出：</strong>false \n",
    "<strong>解释：</strong>s1=&quot;abe&quot; 的所有排列包括：&quot;abe&quot;，&quot;aeb&quot;，&quot;bae&quot;，&quot;bea&quot;，&quot;eab&quot; 和 &quot;eba&quot; ，s2=&quot;acd&quot; 的所有排列包括：&quot;acd&quot;，&quot;adc&quot;，&quot;cad&quot;，&quot;cda&quot;，&quot;dac&quot; 和 &quot;dca&quot;。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = &quot;leetcodee&quot;, s2 = &quot;interview&quot;\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s1.length == n</code></li>\n",
    "\t<li><code>s2.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li>所有字符串都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-a-string-can-break-another-string](https://leetcode.cn/problems/check-if-a-string-can-break-another-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-a-string-can-break-another-string](https://leetcode.cn/problems/check-if-a-string-can-break-another-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n\"xya\"', '\"abe\"\\n\"acd\"', '\"leetcodee\"\\n\"interview\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        # l1,l2=list(str(s1)),list(str(s2))\n",
    "        n=len(s1)\n",
    "        \n",
    "        l=[0]*26\n",
    "        for i in s2:\n",
    "            l[ord(i)-ord('a')]+=1\n",
    "            \n",
    "        for i in range(n):\n",
    "            ch=s1[i]\n",
    "            index=ord(ch)-ord('a')\n",
    "            flag=0\n",
    "            for j in range(index,26):\n",
    "                if l[j]:\n",
    "                    l[j]-=1\n",
    "                    flag=1\n",
    "                    break\n",
    "        \n",
    "            if not flag:break\n",
    "        if flag:return True\n",
    "        \n",
    "        s2,s1=s1,s2\n",
    "        \n",
    "        l=[0]*26\n",
    "        for i in s2:\n",
    "            l[ord(i)-ord('a')]+=1\n",
    "            \n",
    "        for i in range(n):\n",
    "            ch=s1[i]\n",
    "            index=ord(ch)-ord('a')\n",
    "            flag=0\n",
    "            for j in range(index,26):\n",
    "                if l[j]:\n",
    "                    l[j]-=1\n",
    "                    flag=1\n",
    "                    break\n",
    "        \n",
    "            if not flag:break\n",
    "        if flag:return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        def f(s1, cnts):\n",
    "            for c in s1:\n",
    "                i = ord(c)-ord('a')\n",
    "                while i<26:\n",
    "                    if cnts[i]>0:\n",
    "                        cnts[i]-=1\n",
    "                        break\n",
    "                    i+=1\n",
    "                if i==26: return False\n",
    "            return True\n",
    "        def g(s):\n",
    "            res = [0]*26\n",
    "            for c in s:\n",
    "                res[ord(c)-ord('a')] += 1\n",
    "            return res\n",
    "        return f(s1, g(s2)) or f(s2, g(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        length = len(s1)\n",
    "        s1_list = [0] * 26\n",
    "        s2_list = [0] * 26\n",
    "        for index in range(length):\n",
    "            s1_list[ord(s1[index]) - ord('a')] += 1\n",
    "            s2_list[ord(s2[index]) - ord('a')] += 1\n",
    "        return isBreak(s1_list.copy(), s2_list.copy()) or isBreak(s2_list, s1_list)\n",
    "        \n",
    "\n",
    "def isBreak(s1_list, s2_list):\n",
    "    s1_pointer = 0\n",
    "    s2_pointer = 0\n",
    "    while 1:\n",
    "        while s1_pointer < 26 and s1_list[s1_pointer] == 0:\n",
    "            s1_pointer += 1\n",
    "        if s1_pointer == 26:\n",
    "            return True\n",
    "        while s2_pointer < 26 and s2_list[s2_pointer] == 0:\n",
    "            s2_pointer += 1\n",
    "        if s2_pointer == 26:\n",
    "            return False \n",
    "        if s1_pointer > s2_pointer:\n",
    "            return False \n",
    "        elif s1_list[s1_pointer] <= s2_list[s2_pointer]:\n",
    "            s2_list[s2_pointer] -= s1_list[s1_pointer]\n",
    "            s1_pointer += 1\n",
    "        else: \n",
    "            s1_list[s1_pointer] -= s2_list[s2_pointer]\n",
    "            s2_pointer += 1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        st = [0 for _ in range(26)]\n",
    "        for i in range(len(s1)):\n",
    "            st[ord(s1[i]) - ord(\"a\")] -= 1\n",
    "            st[ord(s2[i]) - ord(\"a\")] += 1\n",
    "        ans, flag_one, flag_two = 0, True, True\n",
    "        for i in range(25, -1, -1):\n",
    "            ans += st[i]\n",
    "            if ans < 0:\n",
    "                flag_one = False\n",
    "            elif ans > 0:\n",
    "                flag_two = False\n",
    "\n",
    "        return flag_one or flag_two"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        length = len(s1)\n",
    "        s1_list = [0] * 26\n",
    "        s2_list = [0] * 26\n",
    "        for index in range(length):\n",
    "            s1_list[ord(s1[index]) - ord('a')] += 1\n",
    "            s2_list[ord(s2[index]) - ord('a')] += 1\n",
    "        return isBreak(s1_list.copy(), s2_list.copy()) or isBreak(s2_list, s1_list)\n",
    "        \n",
    "\n",
    "def isBreak(s1_list, s2_list):\n",
    "    s1_pointer = 0\n",
    "    s2_pointer = 0\n",
    "    while 1:\n",
    "        while s1_pointer < 26 and s1_list[s1_pointer] == 0:\n",
    "            s1_pointer += 1\n",
    "        if s1_pointer == 26:\n",
    "            return True\n",
    "        while s2_pointer < 26 and s2_list[s2_pointer] == 0:\n",
    "            s2_pointer += 1\n",
    "        if s2_pointer == 26:\n",
    "            return False \n",
    "        if s1_pointer > s2_pointer:\n",
    "            return False \n",
    "        elif s1_list[s1_pointer] <= s2_list[s2_pointer]:\n",
    "            s2_list[s2_pointer] -= s1_list[s1_pointer]\n",
    "            s1_pointer += 1\n",
    "        else: \n",
    "            s1_list[s1_pointer] -= s2_list[s2_pointer]\n",
    "            s2_pointer += 1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        a1 = [0 for _ in range(26)]\n",
    "        a2 = [0 for _ in range(26)]\n",
    "        for c in s1:\n",
    "            a1[ord(c) - ord('a')] += 1\n",
    "        for c in s2:\n",
    "            a2[ord(c) - ord('a')] += 1\n",
    "\n",
    "        flag1 = True\n",
    "        flag2 = True\n",
    "        acc1, acc2 = 0, 0\n",
    "\n",
    "        for x in range(26):\n",
    "            acc1 += a1[x]\n",
    "            acc2 += a2[x]\n",
    "            if acc1 < acc2:\n",
    "                flag1 = False\n",
    "            if acc2 < acc1:\n",
    "                flag2 = False\n",
    "        return flag1 or flag2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        c1 = Counter(s1)\n",
    "        c2 = Counter(s2)\n",
    "        diff = 0\n",
    "        s = set()\n",
    "        #和排序差不多。也是搭累计\n",
    "        for i in range(26):\n",
    "            c = chr(ord('a') + i)\n",
    "            diff += c1[c] - c2[c]\n",
    "            if diff:\n",
    "                s.add(diff > 0)\n",
    "        return len(s) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        c1 = Counter(s1)\n",
    "        c2 = Counter(s2)\n",
    "        diff = 0\n",
    "        s = set()\n",
    "        for i in range(26):\n",
    "            c = chr(ord('a') + i)\n",
    "            diff += c1[c] - c2[c]\n",
    "            if diff:\n",
    "                s.add(diff > 0)\n",
    "        return len(s) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        count1 = [0] * 26\n",
    "        count2 = [0] * 26\n",
    "        a = ord('a')\n",
    "        for i in range(len(s1)):\n",
    "            count1[ord(s1[i]) - a] += 1\n",
    "            count2[ord(s2[i]) - a] += 1\n",
    "        idx1 = 0\n",
    "        idx2 = 0\n",
    "        mask1 = -1\n",
    "        mask2 = -1\n",
    "        for i in range(len(s1)):\n",
    "            while count1[idx1] == 0:\n",
    "                idx1 += 1\n",
    "            while count2[idx2] == 0:\n",
    "                idx2 += 1\n",
    "            if idx1 > idx2:\n",
    "                mask1 = 1\n",
    "            if idx1 < idx2:\n",
    "                mask2 = 1\n",
    "            count1[idx1] -= 1\n",
    "            count2[idx2] -= 1\n",
    "            if mask1 == mask2 == 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        cnt = [0] * 26\n",
    "        for i in range(len(s1)):\n",
    "            cnt[ord(s1[i]) - ord('a')] -= 1\n",
    "            cnt[ord(s2[i]) - ord('a')] += 1\n",
    "\n",
    "        sum = 0\n",
    "        big1, big2 = True, True\n",
    "        for i in range(25, -1, -1):\n",
    "            sum += cnt[i]\n",
    "            if big1 and sum > 0:\n",
    "                big1 = False\n",
    "            if big2 and sum < 0:\n",
    "                big2 = False\n",
    "            if not big1 and not big2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        def canBreak(s1: str, s2: str) -> bool:\n",
    "            \"\"\" Each char in s1 is larger than that in s2\n",
    "            \"\"\"\n",
    "            dict1 = defaultdict(int)\n",
    "            dict2 = defaultdict(int) \n",
    "            for char in s2:\n",
    "                dict1[char] += 1\n",
    "            for char in s1:\n",
    "                dict2[char] += 1\n",
    "            \n",
    "            # Greedy component\n",
    "            alpha = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "            table = {ch: i for i, ch in enumerate(alpha)}\n",
    "            for ch in dict1:\n",
    "                pos = table[ch] \n",
    "                for i in range(pos, -1, -1):\n",
    "                    cur = alpha[i]\n",
    "                    # print(i, cur, ch)\n",
    "                    if dict1.get(ch, 0) == 0:\n",
    "                        break\n",
    "                    if dict2.get(cur, 0) != 0:\n",
    "                        if dict1[ch] < dict2[cur]:\n",
    "                            dict2[cur] -= dict1[ch]\n",
    "                            dict1[ch] = 0\n",
    "                        else:\n",
    "                            dict1[ch] -= dict2[cur]\n",
    "                            del dict2[cur]\n",
    "                # print(dict1, dict2)\n",
    "            return len(dict2) == 0\n",
    "\n",
    "        return canBreak(s1, s2) or canBreak(s2, s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        c1 = Counter(s1)\n",
    "        c2 = Counter(s2)\n",
    "\n",
    "        chars = [chr(ord('a') + i) for i in range(26)]\n",
    "\n",
    "        acc1 = accumulate(c1[ch] for ch in chars)\n",
    "        acc2 = accumulate(c2[ch] for ch in chars)\n",
    "\n",
    "        acc1, acc2 = list(acc1), list(acc2)\n",
    "\n",
    "        return all(a1 <= a2 for a1, a2 in zip(acc1, acc2)) or \\\n",
    "               all(a1 >= a2 for a1, a2 in zip(acc1, acc2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        #将字符串按字母顺序排序\n",
    "        sorted_str1 = ''.join(sorted(s1))\n",
    "        sorted_str2 = ''.join(sorted(s2))\n",
    "\n",
    "        # 比较两个排序后的字符串\n",
    "        if sorted_str1 < sorted_str2 :\n",
    "           for i in range(1, len(sorted_str1)):\n",
    "                if sorted_str1[i] > sorted_str2[i]:\n",
    "                    return False\n",
    "        elif sorted_str1 > sorted_str2:\n",
    "            for i in range(1, len(sorted_str1)):\n",
    "                if sorted_str1[i] < sorted_str2[i]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        def myfunc(s:str)->str:\n",
    "            l = list(s)\n",
    "            l.sort()\n",
    "            return \"\".join(l)\n",
    "        s1,s2 = myfunc(s1),myfunc(s2)\n",
    "        f1,f2 = True,True\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] < s2[i]:\n",
    "                f1 = False\n",
    "                break\n",
    "        for i in range(len(s1)):\n",
    "            if s2[i] < s1[i]:\n",
    "                f2 = False\n",
    "                break\n",
    "        if f1 or f2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = self.strSort(s1)\n",
    "        s2 = self.strSort(s2)\n",
    "        cur = 0\n",
    "        if s2 > s1:\n",
    "            s1, s2 = s2, s1\n",
    "        while cur < len(s1):\n",
    "            if s1[cur] < s2[cur]:\n",
    "                return False\n",
    "            cur += 1\n",
    "        return True\n",
    "    \n",
    "    \n",
    "\n",
    "    def strSort(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        s.sort(reverse=True)\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        chs1 = list(s1)\n",
    "        chs2 = list(s2)\n",
    "\n",
    "        chs1.sort()\n",
    "        chs2.sort()\n",
    "\n",
    "        return all(c1 >= c2 for c1, c2 in zip(chs1, chs2)) or \\\n",
    "               all(c1 <= c2 for c1, c2 in zip(chs1, chs2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(s1)\n",
    "        s2 = sorted(s2)\n",
    "        return all(s1[i] >= s2[i] for i in range(len(s1))) or all(s1[i] <= s2[i] for i in range(len(s1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = list(s1)\n",
    "        s2 = list(s2)\n",
    "        s1.sort()\n",
    "        s2.sort()\n",
    "        greater,less = 0,0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] > s2[i]:\n",
    "                greater += 1\n",
    "            elif s1[i] < s2[i]:\n",
    "                less += 1\n",
    "        return greater == 0 or less == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\r\n",
    "        s1 = sorted(s1)\r\n",
    "        s2 = sorted(s2)\r\n",
    "        n = len(s1)\r\n",
    "        flag = 0\r\n",
    "        for i in range(n):\r\n",
    "            if s1[i] > s2[i]:\r\n",
    "                flag |= 1\r\n",
    "            elif s1[i] < s2[i]:\r\n",
    "                flag |= 2\r\n",
    "        return flag != 3\r\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        chs1 = list(s1)\n",
    "        chs2 = list(s2)\n",
    "\n",
    "        chs1.sort()\n",
    "        chs2.sort()\n",
    "\n",
    "        return all(c1 >= c2 for c1, c2 in zip(chs1, chs2)) or all(c1 <= c2 for c1, c2 in zip(chs1, chs2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        n =len(s1)\n",
    "        lst1 = list(s1)\n",
    "        lst2 = list(s2)\n",
    "        lst1.sort()\n",
    "        lst2.sort()\n",
    "        if all(lst1[i] >= lst2[i] for i in range(n)) or all(lst1[i] <= lst2[i] for i in range(n)):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        s1 = list(s1)\n",
    "        s2 = list(s2)\n",
    "        s1.sort()\n",
    "        s2.sort()\n",
    "        # print(s1, s2)\n",
    "        flag = None\n",
    "        for i in range(n):\n",
    "            if s1[i] == s2[i]:\n",
    "                continue\n",
    "            elif s1[i] > s2[i]:\n",
    "                if not flag:\n",
    "                    flag = 1\n",
    "                elif flag == -1:\n",
    "                    return False\n",
    "            else:\n",
    "                if not flag:\n",
    "                    flag = -1\n",
    "                elif flag == 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        ss1=sorted(s1)\n",
    "        ss2=sorted(s2)\n",
    "        l = len(s1)\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            if ss1[i]>ss2[i]:\n",
    "                if ans==-1:\n",
    "                    return False\n",
    "                ans=1\n",
    "            elif ss1[i]<ss2[i]:\n",
    "                if ans==1:\n",
    "                    return False\n",
    "                ans=-1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1_sorted = sorted(s1)\n",
    "        s2_sorted = sorted(s2)\n",
    "        \n",
    "        # 检查s1是否可以打破s2\n",
    "        can_s1_break_s2 = all(a >= b for a, b in zip(s1_sorted, s2_sorted))\n",
    "        \n",
    "        # 检查s2是否可以打破s1\n",
    "        can_s2_break_s1 = all(a >= b for a, b in zip(s2_sorted, s1_sorted))\n",
    "        \n",
    "        return can_s1_break_s2 or can_s2_break_s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1_sorted = sorted(s1)\n",
    "        s2_sorted = sorted(s2)\n",
    "        \n",
    "        # 检查s1是否可以打破s2\n",
    "        can_s1_break_s2 = all(a >= b for a, b in zip(s1_sorted, s2_sorted))\n",
    "        \n",
    "        # 检查s2是否可以打破s1\n",
    "        can_s2_break_s1 = all(a >= b for a, b in zip(s2_sorted, s1_sorted))\n",
    "        \n",
    "        return can_s1_break_s2 or can_s2_break_s1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(s1)\n",
    "        s2 = sorted(s2)\n",
    "        return all(c1 >= c2 for c1, c2 in zip(s1, s2)) or all(c1 <= c2 for c1, c2 in zip(s1, s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        return all(x >= y for x,y in zip(sorted(s1),sorted(s2))) or all(x >= y for x,y in zip(sorted(s2),sorted(s1))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        chs1 = list(s1)\n",
    "        chs2 = list(s2)\n",
    "\n",
    "        chs1.sort()\n",
    "        chs2.sort()\n",
    "\n",
    "        return all(c1 >= c2 for c1, c2 in zip(chs1, chs2)) or \\\n",
    "               all(c1 <= c2 for c1, c2 in zip(chs1, chs2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        n=len(s1)\n",
    "        a,b=sorted(s1,reverse=True),sorted(s2,reverse=True)\n",
    "        return all(a[i]>=b[i] for i in range(n)) or all(b[i]>=a[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        #贪心地排列\n",
    "        n=len(s1)\n",
    "        a,b=sorted(s1,reverse=True),sorted(s2,reverse=True)\n",
    "        return all(a[i]>=b[i] for i in range(n)) or all(b[i]>=a[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(s1)\n",
    "        s2 = sorted(s2)\n",
    "        big = None\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            if c1 > c2:\n",
    "                if big == None:\n",
    "                    big = True\n",
    "                elif big == False:\n",
    "                    return False\n",
    "            elif c2 > c1:\n",
    "                if big == None:\n",
    "                    big = False\n",
    "                elif big == True:\n",
    "                    return False\n",
    "                    \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        ls1,ls2 = list(s1),list(s2)\n",
    "        ls1.sort()\n",
    "        ls2.sort()\n",
    "        flag1,flag2 = False,False\n",
    "        for i,j in zip(ls1,ls2):\n",
    "            if i>j:\n",
    "                flag1 = True\n",
    "            elif i<j:\n",
    "                flag2 = True\n",
    "            else:\n",
    "                continue\n",
    "        return not (flag1 and flag2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(s1)\n",
    "        s2 = sorted(s2)\n",
    "        big = None\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            now = c1 > c2\n",
    "            if big == None:\n",
    "                big = now\n",
    "            elif big != now:\n",
    "                return False\n",
    "                    \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        arr1, arr2 = list(s1), list(s2)\n",
    "        arr1.sort()\n",
    "        arr2.sort()\n",
    "        a, b = 0, 0\n",
    "        for i in range(0, len(s1)):\n",
    "            if arr1[i] > arr2[i]:\n",
    "                a += 1\n",
    "            elif arr1[i] < arr2[i]:\n",
    "                b += 1\n",
    "        return a == 0 or b == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(s1)\n",
    "        s2 = sorted(s2)\n",
    "        flag1 = True\n",
    "        flag2 = True\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] < s2[i]:\n",
    "                flag1 = False\n",
    "            if s1[i] > s2[i]:\n",
    "                flag2 = False\n",
    "        return flag1 or flag2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        chs1 = list(s1)\n",
    "        chs2 = list(s2)\n",
    "\n",
    "        chs1.sort()\n",
    "        chs2.sort()\n",
    "\n",
    "        return all(c1 >= c2 for c1, c2 in zip(chs1, chs2)) or \\\n",
    "               all(c1 <= c2 for c1, c2 in zip(chs1, chs2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        s1 = sorted(s1)\n",
    "        s2 = sorted(s2)\n",
    "\n",
    "        return all(x >=y for x,y in zip(s1,s2)) or all(x>=y for x,y in zip(s2,s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        \n",
    "        def cmp(a, b):\n",
    "            ln = len(a)\n",
    "            a = sorted(a)\n",
    "            b = sorted(b)\n",
    "            if all(a[i] >= b[i] for i in range(ln)):\n",
    "                return True \n",
    "            return False \n",
    "        \n",
    "        return cmp(s1, s2) or cmp(s2, s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        list1 = list(s1)\n",
    "        list2 = list(s2)\n",
    "        list1.sort()\n",
    "        list2.sort()\n",
    "        return all(a <= b for a, b in zip(list1, list2)) \\\n",
    "            or all(a >= b for a, b in zip(list1, list2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = list(s1)\n",
    "        s2 = list(s2)\n",
    "        s1.sort()\n",
    "        s2.sort()\n",
    "        counts1,counts2 = 0,0\n",
    "        for i in range(len(s1)):\n",
    "            if ord(s1[i]) - ord('a') >= ord(s2[i]) - ord('a'):\n",
    "                counts1 += 1\n",
    "            if ord(s2[i]) - ord('a') >= ord(s1[i]) - ord('a'):\n",
    "                counts2 += 1\n",
    "        if counts1 == len(s1) or counts2 == len(s2):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        numa = [ord(c) for c in s1]\n",
    "        numb = [ord(c) for c in s2]\n",
    "        numa.sort()\n",
    "        numb.sort()\n",
    "\n",
    "        flag = True\n",
    "        for i in range(n):\n",
    "            if numa[i] < numb[i]:\n",
    "                flag = False\n",
    "        if flag:\n",
    "            return True\n",
    "        \n",
    "        flag = True\n",
    "        for i in range(n):\n",
    "            if numa[i] > numb[i]:\n",
    "                flag = False\n",
    "        if flag:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1_sorted = sorted(s1)\n",
    "        s2_sorted = sorted(s2)\n",
    "        \n",
    "        # 检查s1是否可以打破s2\n",
    "        can_s1_break_s2 = all(a >= b for a, b in zip(s1_sorted, s2_sorted))\n",
    "        \n",
    "        # 检查s2是否可以打破s1\n",
    "        can_s2_break_s1 = all(a >= b for a, b in zip(s2_sorted, s1_sorted))\n",
    "        \n",
    "        return can_s1_break_s2 or can_s2_break_s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(list(s1))\n",
    "        s2 = sorted(list(s2))\n",
    "        flag = 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] > s2[i]:\n",
    "                if not flag:    flag = 1\n",
    "                elif flag == -1:    return False\n",
    "            elif s1[i] < s2[i]:\n",
    "                if not flag:    flag = -1\n",
    "                elif flag == 1:     return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        ss1=sorted(s1)\n",
    "        ss2=sorted(s2)\n",
    "        l = len(s1)\n",
    "        ans = []\n",
    "        for i in range(l):\n",
    "            if ss1[i]>ss2[i]:\n",
    "                ans.append(1)\n",
    "            elif ss1[i]<ss2[i]:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        if 1 in ans and -1 in ans:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(list(s1))\n",
    "        s2 = sorted(list(s2))\n",
    "        return all(s1[i] >= s2[i] for i in range(len(s1))) or \\\n",
    "            all(s2[i] >= s1[i] for i in range(len(s1)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        m = sorted(s1)\n",
    "        n = sorted(s2)\n",
    "        l = len(m)\n",
    "        max_count = 0\n",
    "        min_count = 0\n",
    "        print(m,n)\n",
    "        for i in range(l):\n",
    "            if m[i] >= n[i]:\n",
    "                max_count += 1\n",
    "            if m[i] <= n[i]:\n",
    "                min_count += 1\n",
    "        print(min_count,max_count)\n",
    "        return True if min_count == l or max_count == l else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        mydict = {\"a\":1,\"b\":2,\"c\":3,\"d\":4,\"e\":5,\"f\":6,\"g\":7,\"h\":8,\"i\":9,\"j\":10,\"k\":11,\"l\":12,\"m\":13,\"n\":14,\"o\":15,\"p\":16,\"q\":17,\"r\":18,\"s\":19,\"t\":20,\"u\":21,\"v\":22,\"w\":23,\"x\":24,\"y\":25,\"z\":26}\n",
    "        list1 = list(s1)\n",
    "        list1.sort()\n",
    "        list2 = list(s2)\n",
    "        list2.sort()\n",
    "        if all([mydict[list1[i]] >= mydict[list2[i]] for i in range(len(s1))]) or all([mydict[list1[i]] <= mydict[list2[i]] for i in range(len(s1))]):\n",
    "            return (True)\n",
    "        return (False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        s1 = sorted(list(s1))\n",
    "        s2 = sorted(list(s2))\n",
    "        return all(a >= b for a, b in zip(s1, s2)) or all(a <= b for a, b in zip(s1, s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        list1 = sorted(list(s1))\n",
    "        list2 = sorted(list(s2))\n",
    "\n",
    "        s1_small = True\n",
    "        s2_small = True\n",
    "        for ch1, ch2 in zip(list1, list2):\n",
    "            if ord(ch1) > ord(ch2):\n",
    "                s1_small = False\n",
    "            if ord(ch2) > ord(ch1):\n",
    "                s2_small = False\n",
    "            \n",
    "            if not s1_small and not s2_small:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        return all(x>=y for x,y in zip(sorted(list(s1)),sorted(list(s2)))) or all(x<=y for x,y in zip(sorted(list(s1)),sorted(list(s2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        # 返回a能否打破b\n",
    "        def beat(a, b):\n",
    "            for i in range(n):\n",
    "                if a[i] < b[i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        a, b = sorted(list(s1)), sorted(list(s2))\n",
    "        n = len(s1)\n",
    "        return beat(a, b) or beat(b, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfCanBreak(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        lst1 = []\n",
    "        lst2 = []\n",
    "        for i in range(len(s1)):\n",
    "            lst1.append(int(ord(s1[i])))\n",
    "            lst2.append(int(ord(s2[i])))\n",
    "        lst1.sort()\n",
    "        lst2.sort()\n",
    "        flag = True\n",
    "        print(lst1,lst2)\n",
    "        if sum(lst1) >= sum(lst2):\n",
    "            for i in range(len(lst1)):\n",
    "                if lst1[i]<lst2[i]:\n",
    "                    flag = False\n",
    "        if sum(lst1) <= sum(lst2):\n",
    "            for i in range(len(lst1)):\n",
    "                if lst1[i]>lst2[i]:\n",
    "                    flag = False\n",
    "        return flag"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
